import numpy as np
from collections import deque
import copy

ACTIONS = ['UP', 'RIGHT', 'DOWN', 'LEFT', 'WAIT', 'BOMB']

def vaild_action_filter(game_state):
    """
    filter vaild action
    :game_state The dictionary that describes everything on the board.
    :valid_actions valid action list according to game_state
    """
    x = game_state['self'][3][0]
    y = game_state['self'][3][1]
    field = np.array(game_state["field"]).copy()

    for bomb in game_state["bombs"]:
        (_x, _y), timer = bomb
        field[_x, _y] = 2 # 炸弹
    for other in game_state["others"]:
        name, score, bombs_left, (_x, _y) = other
        field[_x, _y] = 3 # 其他人

    valid_actions = []
    if field[x, y] == 0:
        valid_actions.append(4)
    
    # 能添加炸弹
    if game_state['self'][2]:
        valid_actions.append(5)
    
    # 不能撞墙
    if x >= 1 and field[x - 1,y] == 0:
        valid_actions.append(3)
    if y <= 15 and field[x,y + 1] == 0:
        valid_actions.append(2)
    if x <= 15 and field[x + 1,y] == 0:
        valid_actions.append(1)
    if y >= 1 and field[x,y - 1] == 0:
        valid_actions.append(0)
    
    if len(valid_actions) == 0:
        valid_actions.append(4)

    return valid_actions


def get_bomb_map(game_state,pre_game_state=None):
    """
    返回 map: [T, H, W] map[i,j,k] = 1 说明 i帧之后 (j,k)位置会被炸到
    timer(3)[扔完炸弹的那一帧后一帧的开始] -> timer(2) -> timer(1) -> timer(0) -> explore -> explore
    """
    H,W = game_state['field'].shape
    directions = [(0,-1),(1,0),(0,1),(-1,0)]
    field = game_state['field']
    _bomb_map = np.zeros((6,H,W))
    bombs = copy.copy(game_state['bombs'])
    if pre_game_state is not None:
        pre_bombs = [(bomb[0],bomb[1]-1) for bomb in pre_game_state['bombs']]
        bombs += pre_bombs
    bombs = set(bombs)

    for bomb in bombs:
        (bomb_x,bomb_y),timer = bomb
        for d in range(4):
            for p in range(0,4):
                # p∈{0,1,2,3}表示可以连续炸三个位置
                next_x = bomb_x + directions[d][0] * p 
                next_y = bomb_y + directions[d][1] * p
                # 超出边界不再炸
                if next_x < 0 or next_x >= H or next_y < 0 or next_y >= W:
                    break
                # 遇到墙不再炸
                if field[next_x,next_y] == -1:
                    break
                _bomb_map[timer + 1,next_x,next_y] = 1
                _bomb_map[timer + 2,next_x,next_y] = 1
    return _bomb_map

def get_time_map(bomb_map,game_state):
    """
    我觉得应该做一张时间地图，那个地方什么时间可以到什么时间不可以到，地图的最后一帧是是往后的所有帧
    """
    H,W = game_state['field'].shape
    field = game_state['field']
    _time_map = np.zeros((7,H,W)) # [T, H, W]

    for x in range(H):
        for y in range(W):
            if field[x,y] != 0:
                _time_map[0,x,y] = 1

    for t in range(7):
        for x in range(H):
            for y in range(W):
                if t > 0:
                    _time_map[t,x,y] = _time_map[t-1,x,y]
                if field[x,y] == 1 and t < 6 and bomb_map[t,x,y]==1: # 箱子
                    _time_map[t,x,y] = 0

    for bomb in game_state['bombs']:
        (x, y),timer = bomb
        _time_map[:timer+1,x,y] = 1

    # for other in game_state['others']:
    #     other_x,other_y = other[3]
    #     _time_map[1,other_x,other_y] = 1

    _time_map[:6] += bomb_map

    return _time_map

def search_target_path(game_state,target,pre_game_state=None,next_bomb_time=0):
    """
    寻找从自己的位置到目标位置的路径
    
    考虑因素:
    1. 要躲过炸弹
    2. 路径尽量短
    3. 被炸弹炸到的木桶及时清除

    炸弹爆炸逻辑
    timer(3)[扔完炸弹的那一帧结束时刻] -> timer(2) -> timer(1) -> timer(0) -> explore -> explore
    timer大于等于0是可以通过game_state获取
    return: path: [str]，包含了路径
    """
    
    # 规划路径
    H,W = game_state['field'].shape
    _self = game_state['self'][3]
    bomb_map = get_bomb_map(game_state, pre_game_state)
    time_map = get_time_map(bomb_map,game_state) # [7, H, W]
    bomb_target = target['target_name'] != 'eat_coin'

    directions = [(0,-1),(1,0),(0,1),(-1,0)]
    direction_names = ['DOWN','LEFT','UP','RIGHT','WAIT']
    queue = deque()
    queue.append((target['target_position'],0))
    area = np.ones((H,W),dtype=np.int16) * -1
    cannot_reach = time_map[-1] # [H,W]
    # 找金币和木桶过程中需要躲避炸弹
    all_num = 0
    while len(queue) > 0:
        all_num += 1
        position,steps = queue.popleft()
        for i,direction in enumerate(directions):
            next_x = position[0] + direction[0]
            next_y = position[1] + direction[1]
            # 超出边界
            if next_x < 0 or next_x >= H or next_y < 0 or next_y >= W:
                continue
            # 不能达到
            if cannot_reach[next_x,next_y] != 0:
                continue
            # 已经访问
            if area[next_x,next_y] >= 0:
                continue

            area[next_x,next_y] = i
            queue.append(((next_x,next_y),steps + 1))

    # 根据炸弹信息修正路线
    queue.append((_self,0,0)) # 位置 目前步数 当前动作
    while len(queue) > 0:
        (x,y),steps,offset = queue[-1]
        if offset == 5:
            queue.pop()
            if len(queue) > 0:
                (x,y),steps,offset = queue.pop()
                offset += 1
                queue.append(((x,y),steps,offset))
            else:
                break
            continue
        
        if not bomb_target and target['target_position'] == (next_x,next_y): break

        if offset == 4:
            next_x,next_y = x,y
        else:
            # if offset > 1: offset -= 1
            d = (area[x,y] + offset) % 4 #
            next_x,next_y = x - directions[d][0],y - directions[d][1]
        
        if bomb_target and target['target_position'] == (next_x,next_y) and steps >= next_bomb_time: break

        cannot_reach_next = False
        # 超出边界
        if next_x < 0 or next_x >= H or next_y < 0 or next_y >= W:
            cannot_reach_next = True
        # 不能达到
        elif time_map[min(steps + 1, 6), next_x, next_y] != 0:
            cannot_reach_next = True

        if cannot_reach_next:
            (x,y),steps,offset = queue.pop()
            offset += 1
            queue.append(((x,y),steps,offset))
        else:
            queue.append(((next_x,next_y),steps+1,0))

    # path = []
    path_names = []
    for item in queue:
        (x,y),steps,offset = item
        
        if offset == 4:
            direction = 4
        else:
            direction = (area[x,y] + offset) % 4
        # path.append(direction)
        path_names.append(direction_names[direction])
    
    if bomb_target and len(path_names) == 1:
        path_names[0] = 'BOMB'
    print(target)
    print(path_names)
    return path_names

def can_reach(self,target,field):
    H,W = field.shape
    directions = [(0,-1),(1,0),(0,1),(-1,0)]
    queue = deque()
    queue.append(target)
    visit = set()
    while len(queue) > 0:
        x,y = queue.popleft()
        visit.add((x,y))
        if self[0] == x and self[1] == y:
            return True
        for d in directions:
            next_x,next_y = x+d[0],y+d[1]
            # 不能出界
            if next_x < 0 or next_x >= H or next_y < 0 or next_y >= W:
                continue
            # 不能是障碍物
            if field[next_x,next_y] != 0:
                continue
            # 不能被访问
            if (next_x,next_y) in visit:
                continue
            queue.append((next_x,next_y))
    return False
   
  
 

def state_to_features(game_state: dict) -> np.array:
    """
    *This is not a required function, but an idea to structure your code.*

    Converts the game state to the input of your model, i.e.
    a feature vector.

    You can find out about the state of the game environment via game_state,
    which is a dictionary. Consult 'get_state_for_agent' in environment.py to see
    what it contains.

    :param game_state:  A dictionary describing the current game board.
    :return: np.array
    """
    # This is the dict before the game begins and after it ends
    if game_state is None:
        return None

    # 将 game_state 编码成 [F, H, W] 的3D向量
    # For example, you could construct several channels of equal shape, ...
    
    H,W = game_state['field'].shape
    channels = np.zeros((12,H,W)) # 每一帧有18条信息
    name, score, bombs_left, (self_x, self_y) = game_state['self']
    # 1. 墙壁 0
    x,y = np.where(game_state['field'] == -1)
    for _x,_y in zip(x,y):
        channels[0,_x,_y] = 1

    # 2. 木箱 1
    x,y = np.where(game_state['field'] == 1)
    for _x,_y in zip(x,y):
        channels[1,_x,_y] = 1

    # 3. 炸弹 2-7
    T = 6
    for bomb in game_state['bombs']:
        (x, y), timer = bomb
        channels[2+timer][x,y] = 1

    # 'UP', 'RIGHT', 'DOWN', 'LEFT'
    direction = [(0,-1),(1,0),(0,1),(-1,0)]
    def _place_invaild(i,j,k):
        if channels[2+k,i,j] != 1:
            return
        if channels[2+k+1,i,j] == 0:
            channels[2+k+1,i,j] = 0.7

        for d in range(4):
            for p in range(1,4):
                # p∈{1,2,3}表示可以连续炸三个位置
                next_x = i + direction[d][0] * p 
                next_y = j + direction[d][1] * p
                # 超出边界不再炸
                if next_x < 0 or next_x >= H or next_y < 0 or next_y >= W:
                    break
                # 遇到墙不再炸
                if channels[1,next_x,next_y] == 1:
                    break
                if channels[2+k,next_x,next_y] == 0:
                    channels[2+k,next_x,next_y] = 0.7
                # 炸弹持续两帧，所以要对下一帧进行设置
                if channels[2+k+1,next_x,next_y] == 0:
                    channels[2+k+1,next_x,next_y] = 0.7

    # 设置爆炸会炸到的区域
    [_place_invaild(i,j,k) for i in range(H) for j in range(W) for k in range(T)]

    # 4. 其他人 8-9
    for other in game_state['others']:
        name, score, bombs_left, (x, y) = other
        channels[8,x, y] = 1
        channels[9,x, y] = score

    # 5. 金币位置 10
    for coin in game_state['coins']:
        channels[10,coin[0],coin[1]] = 1

    # 6. 我的位置 11
    name, score, bombs_left, (x, y) = game_state['self']
    channels[11, self_x, self_y] = 1

    # concatenate them as a feature tensor (they must have the same shape), ...
    # stacked_channels = np.stack(channels,axis=0)
    # and return them as a vector ? why 
    return channels